package 打牢基础30天.day04.my;

import java.util.Stack;

/**
 * @Author yaya
 * @Create 2024/6/13 16:07
 * Description:判断链表是否为回文列表
 */
public class Code04_IsPalindromeList {

    public static class Node {
        public int value;
        public Node next;

        Node(int data) {
            this.value = data;
        }
    }

    /**
     * 使用栈结构将所有数据放入栈中，再弹出进行对比，如果相同就是回文
     *
     * @param head
     * @return
     */
    public static boolean isPalindrome1(Node head) {
        if (head == null || head.next == null) {
            return true;
        }
        Stack<Integer> stack = new Stack<>();
        Node temp = head;
        while (temp != null) {
            stack.push(temp.value);
            temp = temp.next;
        }

        temp = head;
        while (temp != null) {
            Integer value = stack.pop();
            if (value != temp.value) {
                return false;
            }
            temp = temp.next;
        }

        return true;
    }

    /**
     * 只使用一半的栈，需要找到中间节点
     * 中间节点：如果是奇数个需要中间节点，如果是偶数个需要虚拟中间的前一个节点
     *
     * @param head
     * @return
     */
    public static boolean isPalindrome2(Node head) {
        if (head == null || head.next == null) {
            return true;
        }
        // 快慢指针，当快指针结束时，慢指针停在中间节点
        Node slow = head;
        Node fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        Stack<Integer> stack = new Stack<>();
        while (slow != null) {
            stack.push(slow.value);
            slow = slow.next;
        }
        while (!stack.isEmpty()) {
            if (head.value != stack.pop()) {
                return false;
            }
        }
        return true;
    }

    /**
     * 终极优化版本，只需要O(1)空间复杂既可以完成回文查询
     *
     * @param head
     * @return
     */
    public static boolean isPalindrome3(Node head) {
        if (head == null || head.next == null) {
            return true;
        }

        Node n1 = head; // slow
        Node n2 = head; // fast

        // 找到中点位置，现在的slow就是中点位置
        if (n2.next != null && n2.next.next != null) {
            n1 = n1.next;  // n1 --> mid
            n2 = n2.next.next;  // n2 --> end
        }

        n2 = n1.next; // 右边first node
        n1.next = null; // n1 --> pre
        Node n3 = null; // n3 --> next

        // 旋转链表
        while (n2 != null) {
            n3 = n2.next;
            n2.next = n1;
            n1 = n2;
            n2 = n3;
        }

        // 旋转后 这个就是right中的first节点， 保存下来供后面还原用
        n3 = n1; // n3 --> save last node
        n2 = head; // n2 --> left first node
        boolean res = true;
        while (n1 != null && n2 != null) {
            if (n1.value != n2.value) {
                res = false;
                break;
            }
            n1 = n1.next;
            n2 = n2.next;
        }
        // 还原链表
        n1 = n3.next;
        n3.next = null;
        while (n1 != null) {
            n2 = n1.next; // n2 --> next
            n1.next = n3; // n3 --> pre
            n3 = n1;
            n1 = n2;
        }

        return res;
    }

    public static boolean isPalindrome4(Node head) {
        if (head == null || head.next == null) {
            return true;
        }

        Node n1 = head;
        Node n2 = head;
        while (n2.next != null && n2.next.next != null) {
            n1 = n1.next; // n1 --> mid
            n2 = n2.next.next; // n2 --> last
        }

        n2 = n1.next; // n2 --> right first node
        Node n3 = null; // n3 --> next
        n1 = null; // n1 --> pre
        // 反转链表
        while (n2 != null) {
            n3 = n2.next;
            n2.next = n1;
            n1 = n2;
            n2 = n3;
        }

        // 判断是否相同
        n3 = n1; // save last node
        n2 = head;
        boolean res = true;
        while (n1 != null && n2 != null) {
            if (n1.value != n2.value) {
                res = false;
            }
            n1 = n1.next;
            n2 = n2.next;
        }

        // 翻转链表
        n2 = null; // pre
        n1 = null; // next
        while (n3 != null) {
            n1 = n3.next;
            n3.next = n2;
            n2 = n3;
            n3 = n1;
        }
        return true;
    }

    public static void printLinkedList(Node node) {
        System.out.print("Linked List: ");
        while (node != null) {
            System.out.print(node.value + " ");
            node = node.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {

        Node head = null;
        printLinkedList(head);
        System.out.print(isPalindrome1(head) + " | ");
        System.out.print(isPalindrome2(head) + " | ");
        System.out.println(isPalindrome3(head) + " | ");
        System.out.println(isPalindrome4(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        printLinkedList(head);
        System.out.print(isPalindrome1(head) + " | ");
        System.out.print(isPalindrome2(head) + " | ");
        System.out.println(isPalindrome3(head) + " | ");
        System.out.println(isPalindrome4(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(2);
        printLinkedList(head);
        System.out.print(isPalindrome1(head) + " | ");
        System.out.print(isPalindrome2(head) + " | ");
        System.out.println(isPalindrome3(head) + " | ");
        System.out.println(isPalindrome4(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(1);
        printLinkedList(head);
        System.out.print(isPalindrome1(head) + " | ");
        System.out.print(isPalindrome2(head) + " | ");
        System.out.println(isPalindrome3(head) + " | ");
        System.out.println(isPalindrome4(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        printLinkedList(head);
        System.out.print(isPalindrome1(head) + " | ");
        System.out.print(isPalindrome2(head) + " | ");
        System.out.println(isPalindrome3(head) + " | ");
        System.out.println(isPalindrome4(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(1);
        printLinkedList(head);
        System.out.print(isPalindrome1(head) + " | ");
        System.out.print(isPalindrome2(head) + " | ");
        System.out.println(isPalindrome3(head) + " | ");
        System.out.println(isPalindrome4(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(1);
        printLinkedList(head);
        System.out.print(isPalindrome1(head) + " | ");
        System.out.print(isPalindrome2(head) + " | ");
        System.out.println(isPalindrome3(head) + " | ");
        System.out.println(isPalindrome4(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(2);
        head.next.next.next = new Node(1);
        printLinkedList(head);
        System.out.print(isPalindrome1(head) + " | ");
        System.out.print(isPalindrome2(head) + " | ");
        System.out.println(isPalindrome3(head) + " | ");
        System.out.println(isPalindrome4(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(2);
        head.next.next.next.next = new Node(1);
        printLinkedList(head);
        System.out.print(isPalindrome1(head) + " | ");
        System.out.print(isPalindrome2(head) + " | ");
        System.out.println(isPalindrome3(head) + " | ");
        System.out.println(isPalindrome4(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");

    }

}
